home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 19 / CU Amiga Magazine's Super CD-ROM 19 (1998)(EMAP Images)(GB)[!][issue 1998-02].iso / CUCD / Programming / LEDA / source / src / dict / _avl_tree.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-11-16  |  3.3 KB  |  168 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  _avl_tree.c
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16. #include <LEDA/impl/avl_tree.h>
  17.  
  18.  
  19. //----------------------------------------------------------------------------
  20. //  avl_tree:
  21. //
  22. //  rebalancing routines for AVL trees
  23. //
  24. //----------------------------------------------------------------------------
  25.  
  26.  
  27. void avl_tree::insert_rebal(avl_tree_item v)
  28. {
  29.   // preconditions:  v is new node created by insertion
  30.   //                 v != root
  31.   //                 height(v) == 1, bal(v) == 0;
  32.  
  33.   // bal(v) == height(R) - height(L)           
  34.  
  35.   //                    u
  36.   //                    |
  37.   //                    v
  38.   //                   / \
  39.   //                  L   R
  40.   //
  41.  
  42.   
  43.   while ( v != root() )
  44.   {
  45.     avl_tree_item u = v->parent;
  46.  
  47.     int dir = (v == u->child[left]) ? left : right;
  48.  
  49.     int b = u->get_bal();
  50.  
  51.     if (dir==left)   // insertion in left subtree of u 
  52.        b--;
  53.     else             // insertion in right subtree of u
  54.        b++; 
  55.  
  56.     u->set_bal(b);
  57.  
  58.     if (b==0)  break;   // height of u has not changed 
  59.  
  60.     if (b != 1 && b != -1)
  61.     { 
  62.       // u is out of balance (-2 or + 2)
  63.  
  64.       int d = (b < 0) ? -1 : +1;
  65.   
  66.       avl_tree_item w = u->child[dir];
  67.   
  68.       if (w->get_bal() == d)
  69.       { rotation(u,w,dir);
  70.         u->set_bal(0);
  71.         w->set_bal(0);
  72.        }
  73.       else
  74.       { avl_tree_item x = w->child[1-dir];
  75.         double_rotation(u,w,x,dir);
  76.  
  77.         if (x->get_bal() == d)
  78.            u->set_bal(-d);
  79.         else
  80.            u->set_bal(0);
  81.   
  82.         if (x->get_bal() == -d)
  83.            w->set_bal(d);
  84.         else
  85.            w->set_bal(0);
  86.   
  87.         x->set_bal(0);
  88.        }
  89.   
  90.       break;
  91.     }
  92.  
  93.     v = u;
  94.  
  95.   }
  96.  
  97. }
  98.  
  99.  
  100. void avl_tree::del_rebal(avl_tree_item v, avl_tree_item)
  101. {
  102.   // precondition:    p is removed inner node
  103.   //                  v is remaining child of p (already linked to parent u)
  104.   //                  v != root
  105.  
  106.   
  107.   while ( v != root() )
  108.   {
  109.     avl_tree_item u = v->parent;
  110.  
  111.     int dir = (v == u->child[left]) ? left : right;
  112.  
  113.     int b = u->get_bal();
  114.  
  115.     if (dir==left)  // deletion in left  subtree of u
  116.        b++;
  117.     else            // deletion in right subtree of u
  118.        b--;
  119.  
  120.     u->set_bal(b);
  121.  
  122.     if (b == 1 || b == -1) break;   // height of u has not changed
  123.  
  124.     if (b != 0)
  125.     { 
  126.       // u is out of balance (-2 or + 2)
  127.  
  128.       int d = (b < 0) ? -1 : +1;
  129.   
  130.       avl_tree_item w = u->child[1-dir];
  131.   
  132.       if (d * w->get_bal() >= 0)
  133.       { rotation(u,w,1-dir);
  134.         if (w->get_bal() == 0)
  135.           { u->set_bal(d);
  136.             w->set_bal(-d);
  137.             break;
  138.            }
  139.         else
  140.           { u->set_bal(0);
  141.             w->set_bal(0);
  142.            }
  143.         v = w;
  144.        }
  145.       else
  146.       { avl_tree_item x = w->child[dir];
  147.         double_rotation(u,w,x,1-dir);
  148.  
  149.         if (x->get_bal() == d)
  150.            u->set_bal(-d);
  151.         else
  152.            u->set_bal(0);
  153.   
  154.         if (x->get_bal() == -d)
  155.            w->set_bal(d);
  156.         else
  157.            w->set_bal(0);
  158.   
  159.         x->set_bal(0);
  160.         v = x;
  161.        }
  162.     }
  163.  
  164.     else v = u;
  165.  
  166.   }
  167. }
  168.